package com.example.java.sort;

import java.util.Arrays;

/**
 * 快速排序
 * @author SOAL
 *
 */
public class QuickSort { 
	
	public static void main(String[] args) {
//		int[] a = {1, 2, 4, 5, 7, 4, 6 ,3 ,9 ,0};
		int[] a = {1, 2, 4, 7, 5, 8, 6 ,3 ,9 };  

        System.out.println(Arrays.toString(a));  
        myQuickSort2(a,0,a.length-1);  
        System.out.println(Arrays.toString(a));  
	}
	
	
	public static void myQuickSort2(int[] a,int low,int high){
		if(low>high){
			return;
		}
		
	 
		int i=low;
		int j=high;
		int key = a[low];//标准值
		
		while(i<j){
			
			while(i<j && a[j]>=key){//j钱移，遇到小于key停止
				j--;
			}
			
			while(i<j && a[i]<=key){ //i后移，遇到大于key停止
				i++;
			}
			
			if(i<j){//交换
				int p=a[i];
				a[i]=a[j];
				a[j]=p;
			}
			
			 
		}
		
		//交换标准值
		int tmp = a[i];
		a[i]=a[low];
		a[low]=tmp;  
		
				
				
		myQuickSort2(a,low,i-1);//排序标准值左边
		myQuickSort2(a,i+1,high);//排序标准值右边
	 
		
	}
		
	
	
	
	
	
	
	
	
	
	
	public static void myQuickSort(int[] a,int low,int high){
		if(low>high){
			return;
		}
		
		int i=low;
		int j=high;
		int key = a[low];
		while(i<j){//不能= 会死循环
			
			while(i<j && a[j]>=key){
				j--;
			}
			
			while(i<j && a[i]<=key){
				i++;
			}
			
			if(i<j){//交换
				int p=a[i];
				a[i]=a[j];
				a[j]=p;
			}
		}
		
		//交换标准值
		int p=a[i];
		a[i]=a[low];
		a[low]=p;
		
		myQuickSort(a,low,i-1);
		myQuickSort(a,i+1,high);

	}
	
	

	/*简介
	快速排序，看这名字就知道这是一种很快的排序方法，实际上也是如此。快速排序属于分治法的一种，就是说通过把数据分成几部分来同时处理的一种算法。这种算法很重要，所以研发岗的面试经常考。

	快速排序的步骤
	我们以数组int[]a={7,5,3,2,9,10,8,4,6,1};这个数组为例来说明一下快速排序到底是怎么进行的。

	第1步：找基准值
	所谓的基准值，顾名思义就是以它为基准进行比大小。通常来说，我们选取数组的第一个数为基准值。在数组a里基准值就是7.

	第2步：比大小
	先从数组的最右边开始往左边找比基准值小的第一个数，然后从数组的最左边开始往右找比基准值大的第一个数。那么为什么要这么找呢？因为现在我们要把数组从小到大排序，所以要找出比基准值小的数放到基准值的左边，找出比基准值的数放在基准值的右边。
	那么在数组a里，从左往右找，第一个比7大的数就是9，我们把它的坐标记为i；从右往左找，第一个比7小的数就是1，我们把它的坐标记为j。

	第3步：交换
	找到之后，如果这个时候i<j，那么就交换这两个数，因为i=4,j=9，符合条件，将9和1进行交换。现在数组变成了int[]a={7,5,3,2,1,10,8,4,6,9};
	如果j>=i，那么不做处理
	为什么还要判断i和j的大小呢？就像第二步说的，我们要找出比基准值小的数放到基准值的左边，找出比基准值的数放在基准值的右边。所以如果i<j的话，交换就达到目的了，如果i>=j，比基准值小的数就在基准值的左边，比基准值大的数已经在基准值的右边了，这时候就没必要交换了。

	第4步：继续查找
	在i<j的前提下，继续向右查找比基准值大的数，往左找比基准值小的数，然后交换。
	在我们的例子中，10和6、8和4都符合交换的条件，所以数组就变成了
	int[]a={7,5,3,2,1,6,4,8,10,9};这时候i=6,j=7

	第5步：交换基准值到合适的位置
	当查找继续进行，这时候i=j=6，已经不满足继续查找和交换的条件了，那么我们应该怎么办呢？答案就是把a[6]和基准值交换，因为i=j的时候说明已经到了一个分界线的位置，分界线左边的数比基准值小，分界线右边的数比基准值大，而这个分界线就是我们的基准值，所以把它和a[i]交换，这时候数组就变成：
	int[]a={4,5,3,2,1,6,7,8,10,9};

	第6步：重复
	对基准值左右两边的两个子数组重复前面五个步骤直至排序完成。

	复杂度
	时间复杂度
	从上面的步骤可以看出来快速排序的快慢取决于区域划分的次数，理想情况下是每次都等分，所以划分次数为logn（即log2n)，时间复杂度为
	T[n] = 2T[n/2] + O(n)其中O(n)为PARTITION()的时间复杂度，对比主定理，

	T[n]= aT[n/b]+f (n)

	我们的快速排序中：a = 2, b = 2, f(n) = O(n)


	最坏的情况就是每次划分之后，一边只有一个元素，另一边有n-1个元素，这样就得划n-1次，这时候时间复杂度为O(n2)

	所以平均的时间复杂度为O(nlogn)

	空间复杂度
	不需要额外的空间，空间复杂度为O(1)

	稳定性
	快速排序算法的稳定性取决于和基准值交换的那个数的大小，如果它们相等的话，那么稳定性就被破坏了，所以快速排序是一种不稳定的排序方法。

	作者：这是朕的江山
	链接：https://www.jianshu.com/p/442399ef0cf7
	來源：简书
	简书著作权归作者所有，任何形式的转载都请联系作者获得授权并注明出处。*/
}


